Trung úy Phêrô Trần Văn Phương sinh năm 1965, tại làng Đơn Sa, xã Quảng Phúc, huyện Quảng Trạch (nay là phường Quảng Phúc, thị xã Ba Đồn), tỉnh Quảng Bình, trong một gia đình nông dân nghèo. Gia đình ông là gia đình tín hữu Công giáo toàn tòng, ông là con trai lớn. Ông mang tên Thánh Phêrô, vị tông đồ trưởng của Hội Thánh và là "Người giữ Chìa khóa Thiên đàng".

Sau khi học xong lớp 10, ông vào bộ đội, được cử đi học lớp kế toán trinh sát pháo binh của quân chủng Hải quân. Tháng 1 năm 1984, ông được bổ sung về làm khẩu đội trưởng pháo thuộc Tiểu đoàn 562, Lữ đoàn 146, Vùng 4 hải quân.

Cuối năm 1985, ông được cử đi học trường Quân chính Quân khu 7. Tháng 1 năm 1986, ông trở về đơn vị, được bổ nhiệm chức vụ Trung đội trưởng và phong quân hàm Thiếu úy.